In [9]:
nx.draw(G2,pos=nx.layout.circular_layout(G2),with_labels=True)
plt.show()
Wang Haihua
🍈 🍉🍊 🍋 🍌
在实际问题中，我们总是希望在完成运输任务的同时，寻求运输费用最低的方案。最小费用流问题，就是要以最小费用从出发点（供应点）将一定的流量输送到接收点（需求点）。在最小流问题中，供应点、需求点的数量可以是一个或多个，但每个供应点的供应量和需求点的需求量是固定的。
最小费用流问题可以用如下的线性规划问题描述
$$ \begin{aligned} &{\min \quad \sum_{i=1}^m\sum_{j=1}^m w_{ij}f_{ij}} \\ s.t.&\left\{\begin{array}{ll} {\displaystyle\sum_{j=1}^{m}f_{ij} -\sum_{j=1}^m f_{ji} = v_i, i=1,2,...,m} \\ {\sum_{i=1}^m v_i=0, i=1,2,...,m} \\ {0\le f_{ij} \le c_{ij}, i=1,2,...,m, j=1,2,...,m} \end{array}\right. \end{aligned} $$求解最小费用流问题的方法很多，常见的如：连续最短路算法（Successive shortest path）、消圈算法（Cycle canceling）、原始对偶算法（Primal dual）、网络单纯性算法（Network simplex）和非均衡网络流算法（Out of Kilter法）等。
网络单纯形是单纯形算法的一个特殊应用，它使用生成树基来更有效地解决具有纯网络形式的线性规划问题。网络单纯性为最小费用流问题提供了标准的解决方法，可以解决数万个节点的大型问题。
最小费用流问题最重要的应用是配送网络的优化，如确定如何从出发地运送到中转站再转运到客户的配送方案。运输问题、指派问题、转运问题、最大流问题、最短路径问题，都是特殊情况下的最小费用流问题。例如，最短路径问题是流量 v=1 的最小费用流问题，最大流问题是最大流量下的最小费用流问题。只要选定合适的权重、容量、流量，解决最小费用流的方法就能用来解决上述问题。
下表表示了两点之间的费用矩阵：
| a | b | c | d | e | f | g | h | i | j | |
|---|---|---|---|---|---|---|---|---|---|---|
| a | 0 | 3 | 5 | 7 | 0 | 1 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 6 | 2 |
| c | 0 | 0 | 0 | 3 | 0 | 2 | 0 | 0 | 1 | 0 |
| d | 0 | 0 | 0 | 0 | 3 | 0 | 6 | 4 | 0 | 0 |
| e | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 6 |
| f | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 |
| g | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 |
| h | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 3 |
| i | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
| j | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
另一张表表示两点之间的容量矩阵：
| a | b | c | d | e | f | g | h | i | j | |
|---|---|---|---|---|---|---|---|---|---|---|
| a | 0 | 6 | 8 | 3 | 0 | 3 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 10 | 5 |
| c | 0 | 0 | 0 | 4 | 0 | 4 | 0 | 0 | 3 | 0 |
| d | 0 | 0 | 0 | 0 | 3 | 0 | 6 | 4 | 0 | 0 |
| e | 0 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 4 |
| f | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 |
| g | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 |
| h | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 1 |
| i | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
| j | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
我们可以利用NetworkX中的min_cost_flow_cost 进行求解得到下图：
import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx # 导入 NetworkX 工具包
import pandas as pd
import random
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus']=False
W = np.array([[ 0, 3, 5, 7, 0, 1, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 9, 6, 2],
[ 0, 0, 0, 3, 0, 2, 0, 0, 1, 0],
[ 0, 0, 0, 0, 3, 0, 6, 4, 0, 0],
[ 0, 1, 0, 0, 0, 0, 0, 0, 4, 6],
[ 0, 0, 0, 0, 0, 0, 0, 4, 0, 0],
[ 0, 0, 0, 0, 7, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 1, 0, 1, 3],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 3],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
C = np.array([[ 0, 6, 8, 3, 0, 3, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 0, 7, 10, 5],
[ 0, 0, 0, 4, 0, 4, 0, 0, 3, 0],
[ 0, 0, 0, 0, 3, 0, 6, 4, 0, 0],
[ 0, 7, 0, 0, 0, 0, 0, 0, 3, 4],
[ 0, 0, 0, 0, 0, 0, 0, 4, 0, 0],
[ 0, 0, 0, 0, 7, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0, 0, 1, 0, 3, 1],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 3],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
df_w = pd.DataFrame(W,index=list('abcdefghij'),columns=list('abcdefghij'))
df_c = pd.DataFrame(C,index=list('abcdefghij'),columns=list('abcdefghij'))
print(df_c.to_markdown())
| | a | b | c | d | e | f | g | h | i | j | |:---|----:|----:|----:|----:|----:|----:|----:|----:|----:|----:| | a | 0 | 6 | 8 | 3 | 0 | 3 | 0 | 0 | 0 | 0 | | b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 10 | 5 | | c | 0 | 0 | 0 | 4 | 0 | 4 | 0 | 0 | 3 | 0 | | d | 0 | 0 | 0 | 0 | 3 | 0 | 6 | 4 | 0 | 0 | | e | 0 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 4 | | f | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | | g | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | 0 | | h | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 | 1 | | i | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | | j | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx # 导入 NetworkX 工具包
# 2. 最小费用流问题（Minimum Cost Flow，MCF）
# 创建有向图
G2 = nx.DiGraph() # 创建一个有向图 DiGraph
G2.add_edges_from([(i,j,{'capacity':df_c.loc[i,j],'weight':df_w.loc[i,j]}) for i in df_c.index for j in df_c.index if df_c.loc[i,j]>0]) # 添加边的属性 'capacity', 'weight'
# 整理边的标签，用于绘图显示
edgeLabel1 = nx.get_edge_attributes(G2, 'capacity')
edgeLabel2 = nx.get_edge_attributes(G2, 'weight')
edgeLabel = {}
for i in edgeLabel1.keys():
edgeLabel[i] = f'({edgeLabel1[i]:},{edgeLabel2[i]:})' # 边的(容量，成本)
nx.draw(G2,pos=nx.layout.circular_layout(G2),with_labels=True)
plt.show()
# v = input("Input flow (v>=0):")
v = 0
while True:
v += 1 # 最小费用流的流量
G2.add_node("a", demand=-v) # nx.min_cost_flow() 的设置要求
G2.add_node("j", demand=v) # 设置源点/汇点的流量
try:
# 求最小费用流(demand=v)
minFlowCost = nx.min_cost_flow_cost(G2) # 求最小费用流的费用
minFlowDict = nx.min_cost_flow(G2) # 求最小费用流
# minFlowCost, minFlowDict = nx.network_simplex(G2) # 求最小费用流--与上行等效
print("流量: {:2d}\t最小费用:{}".format(v, minFlowCost)) # 输出最小费用的值(demand=v)
# print("最小费用流的路径及流量: ", minFlowDict) # 输出最大流的途径和各路径上的流量
except Exception as e:
print("流量: {:2d}\t超出网络最大容量，没有可行流。".format(v))
print("\n流量 v={:2d}：计算最小费用流失败({})。".format(v, str(e)))
break # 结束 while True 循环
流量: 1 最小费用:5 流量: 2 最小费用:10 流量: 3 最小费用:15 流量: 4 最小费用:20 流量: 5 最小费用:25 流量: 6 最小费用:33 流量: 7 最小费用:42 流量: 8 最小费用:51 流量: 9 最小费用:60 流量: 10 最小费用:76 流量: 11 最小费用:92 流量: 12 最小费用:108 流量: 13 最小费用:127 流量: 14 超出网络最大容量，没有可行流。 流量 v=14：计算最小费用流失败(no flow satisfies all node demands)。
edgeLists = []
for i in minFlowDict.keys():
for j in minFlowDict[i].keys():
edgeLabel[(i, j)] += ',f=' + str(minFlowDict[i][j]) # 取出每条边流量信息存入边显示值
if minFlowDict[i][j] > 0:
edgeLists.append((i, j))
maxFlow = sum(minFlowDict['a'][j] for j in minFlowDict['a'].keys()) # 求最大流量的值
print("\n最大流量: {:2d},\t最小费用:{}".format(maxFlow, minFlowCost)) # 输出最小费用的值
print("最小费用流的路径及流量: ", minFlowDict) # 输出最小费用流的途径和各路径上的流量
print("最小费用流的路径：", edgeLists) # 输出最小费用流的途径
最大流量: 13, 最小费用:127
最小费用流的路径及流量: {'a': {'b': 5, 'c': 2, 'd': 3, 'f': 3}, 'b': {'h': 0, 'i': 0, 'j': 5}, 'c': {'d': 0, 'f': 0, 'i': 2}, 'd': {'e': 3, 'g': 0, 'h': 0}, 'f': {'h': 3}, 'h': {'g': 1, 'i': 1, 'j': 1}, 'i': {'j': 3}, 'j': {}, 'e': {'b': 0, 'i': 0, 'j': 4}, 'g': {'e': 1}}
最小费用流的路径： [('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'f'), ('b', 'j'), ('c', 'i'), ('d', 'e'), ('f', 'h'), ('h', 'g'), ('h', 'i'), ('h', 'j'), ('i', 'j'), ('e', 'j'), ('g', 'e')]
# 绘制有向网络图
plt.figure(figsize=(10,7))
plt.title("Minimum Cost Maximum Flow with NetworkX")
pos=s=nx.layout.circular_layout(G2)
nx.draw(G2,pos,with_labels=True,node_color='c',node_size=300,font_size=20) # 绘制有向图，显示顶点标签
nx.draw_networkx_edge_labels(G2,pos,edgeLabel,font_size=10) # 显示边的标签：'capacity','weight' + minCostFlow
nx.draw_networkx_edges(G2,pos,edgelist=edgeLists,edge_color='m',width=2) # 设置指定边的颜色、宽度
plt.axis('on')
plt.savefig('images/opt0901.png')
plt.show()
